/**
 * @a https://leetcode.cn/problems/cut-off-trees-for-golf-event/
 */

#include "../../common.h"

class Solution {
    using PII=pair<int,int>;
    int row;
    int col;
    map<int, PII> treeHightPoint;

private:
    int two_pointdistance(vector<vector<int>>& forest, int start, int end){
        if(start == end) return 0;
        if(start == 0 || end == 0) return -1;
        
        const static int dx[4] = {0,0,1,-1};
        const static int dy[4] = {1,-1,0,0};

        auto [x,y] = treeHightPoint[start];
        int ret = 0;
        vector<vector<bool>> local_vis(row,vector<bool>(col,false));
        queue<PII> que;
        que.push(treeHightPoint[start]);
        local_vis[x][y] = true;

        while(que.size()){
            int sz = que.size();
            ++ret;
            while(sz--){
                auto [a,b] = que.front();
                que.pop();
                for(int i = 0; i < 4; ++i){
                    int x = a + dx[i], y = b + dy[i];
                    if(x >= 0 && x < row && y >= 0 && y < col 
                        && forest[x][y] != 0 && local_vis[x][y] == false){
                        if(forest[x][y] == end) return ret;

                        que.push({x,y});
                        local_vis[x][y] = true;
                    }
                }

            }
        }
        return -1;
    }

public:
    int cutOffTree(vector<vector<int>>& forest) {
        if(forest[0][0] == 0) return -1;

        row = forest.size();
        col = forest[0].size();
        vector<int> treeCutOrder;
        for(int i = 0; i < row; ++i){
            for(int j = 0; j < col; ++j){
                int var = forest[i][j];
                if(var != 0 && var != 1) 
                {
                    treeHightPoint.insert({var,{i,j}});
                    treeCutOrder.push_back(var);
                }
            }
        }
        sort(treeCutOrder.begin(), treeCutOrder.end());

        int sz = treeCutOrder.size();
        int ret = two_pointdistance(forest, forest[0][0], treeCutOrder[0]);
        for(int i = 0; i < sz - 1; ++i)
        {
            int tmp = two_pointdistance(forest, treeCutOrder[i], treeCutOrder[i + 1]);
            
            if(tmp == -1) return -1;
            ret += tmp;
        }

        return ret;
    }
};